The present invention basically relates to the general field of data unit communication. In data unit communication, an amount of data is divided into individual units, and said units are transmitted to a desired receiver over an appropriate communication path. This form of data communication is very well known and in wide use.
Such data units carry a variety of names in the context of different communication systems and communication protocols, such as packets, frames, segments, protocol data units, etc. The term “data unit” as used in the present specification and claims generically refers to any such division of a data amount.
In order to ensure the complete transmission of data units from a sender to a receiver, a mechanism referred to as ARQ (Automatic Retransmission reQuest) is known. When using an ARQ mechanism, the receiver of data units sends feedback messages to the sender, such that the sender can determine whether sent data units were properly received, and if not, to appropriately perform retransmissions of data units.
It can also occur that the communication of data units from a given sender to a given receiver occurs via one or more relay points. One example of such a situation is if a desk top computer communicates with a portable computer that has a WLAN module, where the communication is handled via a WLAN router. Another example of such a situation is if a link layer (layer 2) communication between a sender and receiver occurs over several relay points. Such connections are also referred to as multi-hop connections.
The basic problem encountered with such multi-hop connections is how to provide a reliable transmission of data units from the sender (i.e. the sending end-point) to the receiver (i.e. the receiving end-point). The paper “A comparison of Mechanisms for Improving TCP Performance over Wireless Links” by H. Balakrishnan et al, Proc. ACM SIGCOMM'96, Stanford, Calif., August 1996, gives an overview of techniques for dealing with multi-hop connections that involve wireless links.
One known solution to the multi-hop problem is the provision of split connections. An example of this principle is shown in FIG. 1. In the example of FIG. 1, a link layer (layer 2) communication between a sender 10 and receiver 12 via a relay device 11 is considered. In order to provide reliable transmission of layer 2 data units, a sending peer 10_2 in sender 10 and a receiving peer 11_2b in the relay device 11 implement an ARQ mechanism, and furthermore a sending peer 11_2a of relay device 11 and a receiving peer 12_2 of receiver 12 implement another ARQ mechanism. In this way, the first ARQ mechanism provides for reliability from sender 10 to relay device 11, and the second ARQ mechanism provides for reliability in the communication from relay device 11 to receiver 12. Naturally, this split connection concept is applicable to any layer, not just the link layer. Nonetheless, it suffers from the disadvantage that if any problems occur in the relay device 11, or a handover from the shown relay device 11 to another relay device becomes necessary, then the entire end-to-end communication is in jeopardy. More specifically, it can occur that the sender 10 has completed its communication with the relay device 11, as the correct receipt of data units at relay 11 has been acknowledged to sender 10, and thereafter a problem occurs in relay device 11, such that some of these data units are lost. In such an event, these data units will be irrevocably lost at the given protocol level (L2 in the example), as the sender has already completed its communication and consequently deleted the data units from its send buffer.
In order to avoid such problems, it is known to introduce sub-layering. This is shown in an example in FIG. 2. The example again relates to a link layer communication between a sender 20 and a receiver 22. In order to provide end-to-end reliability, the link layer L2 is divided into two sub-layers, where the upper sub-layer has two peers 20_2′ and 22_2′ located at the sender 20 and receiver 22, respectively. These two peers implement their own ARQ mechanism, in order to provide for retransmission if data units of this upper sub-layer are lost on the end-to-end connection. Additionally, a lower sub-layer is provided, having respective peers 20_2 and 21_2b between sender 20 and relay device 21, and 21_2a and 22_2 between relay device 21 and receiver 22. The data units of the upper sub-layer are encapsulated or segmented into data units of the lower sub-layer, and each lower sub-layer peer pair has its own ARQ mechanism. Modifications of this sub-layering concept are known, e.g. U.S. Pat. No. 5,699,367 describes a situation, where the lower sub-layer is only provided on one hop, e.g. only between sender 20 and relay device 21.
Due to the end-to-end ARQ mechanism of peers 20_2′ and 22_2′, problems in the relay device 21 do not lead to irrevocable data unit loss. On the other hand, the ARQ mechanisms on the hops from sender to relay device and relay device to receiver ensure resource efficient and fast error recovery over each hop, e.g. by avoiding unnecessary end-to-end retransmissions. Nonetheless, the concept of sub-layering has the disadvantage of requiring complicated adjustment of the ARQ control in the upper sub-layer and lower sub-layer, in order to avoid ARQ conflicts, which can e.g. lead to unnecessary redundant data transmission, which in turn degrades the end-to-end performance.
In order to provide an improved concept for reliable data unit transmission from a sender to a receiver via a relay device, the applicant/assignee of the present application has filed a patent application PCT/EP2004/009967, which is herewith fully incorporated by reference. In PCT/EP2004/009967, a novel concept and protocol is disclosed, according to which data units are sent from a sending peer to a receiving peer via one or more relay peers, where said protocol provides for a first and a second type of receipt information, said first type indicating the correct receipt at a relay peer, and the second type indicating the correct receipt at the receiving peer. This concept will be referred to as Relay-ARQ or RARQ in the following.
This basic concept of Relay-ARQ is shown in FIG. 3. A data unit communication between a sender 30 and a receiver 32 via a relay device 31 is handled in one layer, where the sender 30 comprises a sending peer 30_2 and the receiver 32 a receiving peer 32_2, and the relay device 31 carries a relay peer 31_2. The communication occurs in accordance with a communication protocol for the sending peer, relay peer and receiving peer, where this communication protocol has a feed-back mechanism, and the feed-back messages are such that they carry information on the receipt of data units. The communication protocol provides for at least a first type and a second type of receipt information, where the first type of receipt information is indicative of a correct receipt of a data unit at the relay peer (31_2 in the example of FIG. 3) and the second type of receipt information is indicative of a correct receipt of a data unit at the final destination peer (32_2 in the example of FIG. 3) of the protocol. The sending peer (30_2 in the example of FIG. 3) performs a first retransmission control procedure for a sent data unit for which no first type receipt information has been received, and a second receipt retransmission control procedure for a sent data unit if the first type receipt information has been received. Namely, looking at the example of FIG. 3, not having received first type receipt information means that the relay peer 31_2 has not acknowledged correct receipt. On the other hand, receiving the first receipt information means that the relay peer 31_2 has acknowledged correct receipt. Nonetheless, the sender holds a data unit in its buffer at least until having received the second type of receipt information, namely information that indicates that the data unit in question has been received at the final destination (receiving peer 32_2 in the example of FIG. 3).
The relay peer is arranged to on the one hand send sender-side feedback messages to the sending peer (30 in the example of FIG. 3), which feedback messages provide the first type of receipt information when a data unit was correctly received from the sending peer 30_2. On the other hand, the relay peer generates send data units based on the receive data units, and transmits these send data units to the receiving peer. The receive data units (i.e. the data units received from the sending peer) and the send data units (i.e. the data units transmitted to the receiving peer) use the same sequence position identifiers. When the relay peer receives a feedback message on the receiver-side (from the receiving peer 32_2 in the example of FIG. 3), then it generates a sender-side feedback message directed towards the sender-side peer (the sending peer 30_2 in the example of FIG. 3) carrying the second type of receipt information for the given sequence position identifier that was already associated with the second type of receipt information in the receiver-side feedback message. Expressed in other words, when the relay peer receives an acknowledgement that a data unit has been correctly received at the final destination peer, then such an acknowledgement is passed on towards the sender.
Based on the use of two different kinds of receipt information, one for indicating correct receipt at a relay device and another for indicating correct receipt at the final destination, the sender and the relay device (or several relay devices, if more than one relay device is involved) can appropriately manage their own retransmission function and buffer management, while both end-to-end-reliability and reliability on individual hops is ensured. This is achieved without the necessity of sub-layering, and consequently without the complexities or problems that occur due to ARQ conflicts between different sub-layers.
This provides a highly reliable mechanism for multi-hop data unit communication that is very simple at the same time.
Despite the above described advantages, it can occur that a transition from one data unit format to another becomes necessary, e.g. when one or more hops are over a wire-line network and one or more other hops are over a wire-less network that uses a different protocol and different format.